package com.problem;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/basic-calculator/
 */
public class BasicCalculator {

    //实现一个基本的计算器来计算一个简单的字符串表达式的值。
    //字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。
    //示例 1:
    //输入: "1 + 1"
    //输出: 2

    //示例 2:
    //输入: " 2-1 + 2 "
    //输出: 3

    //示例 3:
    //输入: "(1+(4+5+2)-3)+(6+8)"
    //输出: 23

    public  void main1(String[] args) {
        String s = "(1+(4+5+2)-3)+(6+8)";

        String a = s.replaceAll("\\(","|").replaceAll("\\)","|");
        //|1+|4+5+2|-3|+|6+8|
        String[] aaa = a.split("|");
        String b = "";
        for (String st : aaa) {
            b+= abc1(st);
        }
        System.out.println(abc1(b));
    }

    private String abc1(String s) {
        s = s.replaceAll("\\+-","-").
                replaceAll("--","\\+");
        String f = "";
        if (s.endsWith("+") || s.endsWith("-")) {
            f = s.substring(s.length()-1);
            s = s.substring(0,s.length()-1);
        }
        List<Integer> iii = new ArrayList<>();
        List<String> sss = new ArrayList<>();
        int n = 0;
        String ns = "";
        //-1-1
        if (s.startsWith("-")) {
            String a = s.replace("-","");
            if (!a.contains("+") && !a.contains("-")) {
                return s;
            }
        }
        if (!s.contains("+") && !s.contains("-")) {
            return s+f;
        }
        for (int i = 0; i < s.length(); i++) {
            if ((i==0 && ('+' == s.charAt(i) && '-' == s.charAt(i))) ||
                    '+' != s.charAt(i) && '-' != s.charAt(i)) {
                //数字
                ns += String.valueOf(s.charAt(i));
            } else {
                //System.out.println(ns);
                iii.add(Integer.parseInt(ns));
                sss.add(String.valueOf(s.charAt(i)));
                ns="";
            }
        }
        if (!"".equals(ns)) {
            iii.add(Integer.parseInt(ns));
        }

        for (int i = 0;i<iii.size();i++) {
            if (i == 0) {
                n = iii.get(0);
            } else {
                if ("+".equals(sss.get(i-1))) {
                    n+= iii.get(i);
                } else if ("-".equals(sss.get(i-1))) {
                    n -= iii.get(i);
                }
            }
        }
        return String.valueOf(n)+f;
    }


    //todo 会超时
    public int calculate(String s) {
        s = s.replaceAll(" ","");
        //System.out.println("s:"+s);
        if (!s.contains("(")) {
            return abc(s);
        } else {
            //(1+(4+5+2)-3)+(6+8)
            return abcdef(s);
        }


//        Stack<String> data = new Stack();
//
//        //1-(2+3-(4+(5-(1-(2+4-(5+6))))))
//        String a = "";
//        for (int i=0;i<s.length();i++) {
//
//            if (')' != s.charAt(i)) {
//                data.push(String.valueOf(s.charAt(i)));
//            } else {
//                for (;; ){
//                    if (!"(".equals(data.peek())) {
//                        a += data.pop();
//                    } else {
//                        break;
//                    }
//                }
//                if (a != "") {
//                    String x = "";
//                    for (int m=a.length()-1;m>-1;m--) {
//                        x+= String.valueOf(a.charAt(m));
//                    }
//                    data.push(abc(x)+"");
//                }
//            }
//        }
//
//        String l = "";
//        while (!data.empty()) {
//            l += data.pop();
//        }
//
//        l = l.replaceAll("\\(","").replaceAll("\\)","").replaceAll("\\+-","-").
//                replaceAll("--","\\+");
//        return abc(l);

    }


    private int abc(String s) {
        s = s.replace("(","");
        s = s.replace(")","");
        List<Integer> iii = new ArrayList<>();
        List<String> sss = new ArrayList<>();
        int n = 0;
        String ns = "";
        //-1-1
        if (s.startsWith("-")) {
            String a = s.replace("-","");
            if (!a.contains("+") && !a.contains("-")) {
                return Integer.valueOf(s);
            }
        }
        if (!s.contains("+") && !s.contains("-")) {
            return Integer.valueOf(s);
        }
        for (int i = 0; i < s.length(); i++) {
            if ((i==0 && ('+' == s.charAt(i) && '-' == s.charAt(i))) ||
                    '+' != s.charAt(i) && '-' != s.charAt(i)) {
                //数字
                ns += String.valueOf(s.charAt(i));
            } else {
                //System.out.println(ns);
                iii.add(Integer.parseInt(ns));
                sss.add(String.valueOf(s.charAt(i)));
                ns="";
            }
        }
        if (!"".equals(ns)) {
            iii.add(Integer.parseInt(ns));
        }

        for (int i = 0;i<iii.size();i++) {
            if (i == 0) {
                n = iii.get(0);
            } else {
                if ("+".equals(sss.get(i-1))) {
                    n+= iii.get(i);
                } else if ("-".equals(sss.get(i-1))) {
                    n -= iii.get(i);
                }
            }
        }
        return n;
    }


    private int abcdef(String s) {
        //(1+(4+5+2)-3)+(6+8)
        for (int i=0;i<s.length();i++) {
            if (!s.contains("(") && !s.contains(")")) {
                break;
            }
            if (')' == s.charAt(i)){
                String sb = s.substring(0,i);
                for (int j=sb.length() -1;j>=0;j--) {
                    if ('(' == sb.charAt(j)) {
                        String sssbb = sb.substring(j+1,i);
                        //sssbb.replace("(","").replace(")","");
                        s = s.replace("(" + sssbb+")",String.valueOf(abc(sssbb))).replace("--","+").replace("+-","-");
                        return abcdef(s);
                    }
                }
            }
        }
        return abc(s);
    }

    public static void main(String[] args) {
        BasicCalculator bc = new BasicCalculator();
        System.out.println(bc.ffff("1-(2+3-(4+(5-(1-(2+4-(5+6))))))"));
//        System.out.println(bc.ffff("(1+(4+5+2)-3)+(61+8)"));
//        System.out.println(bc.ffff("2-(5-6)"));
//       System.out.println(bc.ffff("1 + 1"));
//      System.out.println(bc.ffff(" 2-1 + 2 "));

    }

    public int xxx(String s) {

        s = s.replaceAll("\\(","|").replaceAll("\\)","|").replaceAll(" ","");;
        //|1+|4+5+2|-3|+|6+8|
        String[] aaa = s.split("\\|");
        String b = "";
        for (String st : aaa) {
            b+= abc1(st);
        }
        return Integer.valueOf(abc1(b));
    }

    //最优答案
    public int ffff(String s) {
        int res=0, sign=1, n=s.length();
        Stack<Integer> st = new Stack<>();
        for(int i=0;i<n;++i){
            char c=s.charAt(i);
            if(c > '0'){
                int num=0;
                while(i<n && s.charAt(i)>='0'){
                    num=num*10+(s.charAt(i)-'0');
                    i++;
                }
                res=res+sign*num;
                i--;
            } else if(c=='+')
                sign=1;
            else if(c=='-')
                sign=-1;
            else if(c=='('){
                st.push(res);
                st.push(sign);
                res=0;
                sign=1;
            }
            else if(c==')'){
                res *= st.pop();
                res += st.pop();
            }
        }
        return res;
    }
}
